﻿//bool Insert(const pair<K, V>& kv)
//{
//	if (_root == nullptr)
//	{
//		_root = new Node(kv);
//		return true;
//	}
//
//	Node* parent = nullptr;
//	Node* cur = _root;
//	while (cur)
//	{
//		if (cur->kv.first < kv.first)
//		{
//			parent = cur;
//			cur = cur->_right;
//		}
//		else if (cur->kv.first > kv.first)
//		{
//			parent = cur;
//			cur = cur->_left;
//		}
//		else
//		{
//			return false;
//		}
//	}
//
//	cur = new Node(kv);
//	if (parent->_kv.first < kv.first)
//	{
//		parent->_right = cur;
//	}
//	else
//	{
//		parent->_left = cur;
//	}
//	cur->_parent = parent;
//
//	while (parent)
//	{
//		if (cur == parent->left)
//		{
//			parent->_bf--;
//		}
//		else
//		{
//			parent->_bf++;
//		}
//
//		if (parent->_bf == 0)
//		{
//			break;
//		}
//		else if (parent->_bf == 1 || parent->_bf == -1)
//		{
//			cur = cur->_parent;
//			parent = parent->_parent;
//		}
//		else if (parent->_bf == 2 || parent->_bf == -2)
//		{
//			// 旋转处理
//			if (parent->_bf == 2 && cur->_bf == 1)
//			{
//				RotateL(parent);
//			}
//			else if (parent->_bf == -2 && cur->_bf == -1)
//			{
//				RotateR(parent);
//			}
//			else if (parent->_bf == -2 && cur->_bf == 1)
//			{
//				RotateLR(parent);
//			}
//			else
//			{
//				RotateRL(parent);
//			}
//			break;
//		}
//		else
//		{
//			// 插入之前AVL树就有问题
//			assert(false);
//		}
//	}
//
//	return true;
//}

//int _Height(Node* root)
//{
//	if (root == nullptr)
//		return 0;
//
//	int leftHeight = _Height(root->_left);
//	int rightHeight = _Height(root->_right);
//
//	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
//}
//
//int Height()
//{
//	return _Height(_root);
//}

//bool _IsBalance(Node* root)
//{
//    if (root == nullptr)
//    {
//        return true;
//    }
//
//	int leftHeight = Height(root->_left);
//	int rightHeight = Height(root->_right);
//
//	if (abs(rightHeight - leftHeight) >= 2)
//	{
//		cout << root->_kv.first << "不平衡" << endl;
//		return false;
//	}
//
//	if (rightHeight - leftHeight != root->_bf)
//	{
//		cout << root->_kv.first << "平衡因子异常" << endl;
//		return false;
//	}
//
//	return _IsBalance(root->_left)
//		&& _IsBalance(root->_right);
//}

//bool _IsBalance(Node* root, int& height)
//{
//	if (root == nullptr)
//	{
//		height = 0;
//		return true;
//	}
//
//	int leftHeight = 0, rightHeight = 0;
//	if (!_IsBalance(root->_left, leftHeight)
//		|| !_IsBalance(root->_right, rightHeight))
//	{
//		return false;
//	}
//
//	if (abs(rightHeight - leftHeight) >= 2)
//	{
//		cout << root->_kv.first << "不平衡" << endl;
//		return false;
//	}
//
//	if (rightHeight - leftHeight != root->_bf)
//	{
//		cout << root->_kv.first << "平衡因子异常" << endl;
//		return false;
//	}
//
//	height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
//
//	return true;
//}
//
//bool IsBalance()
//{
//	int height = 0;
//	return _IsBalance(_root, height);
//}

//#include <algorithm>
//#include <iostream>
//#include <vector>
//using namespace std;
//
//int main() {
//    int num = 0;
//    cin >> num;
//    while (num--)
//    {
//        int n, k;
//        cin >> n >> k;
//        int count = 2 * n;
//        vector<int> v1;
//        while (count--)
//        {
//            int tmp = 0;
//            cin >> tmp;
//            v1.push_back(tmp);
//        }
//
//        //得到了牌序列
//        //每次洗牌排序列要改变
//
//        while (k--)
//        {
//            vector<int> v2;
//
//            //洗牌
//            for (int i = n - 1; i >= 0; i--)
//            {
//                v2.push_back(v1[i + n]);
//                v2.push_back(v1[i]);
//            }
//
//            reverse(v2.begin(), v2.end());
//
//            //每次洗完将v2赋值给v1形成新的牌
//            v1 = v2;
//        }
//        for (auto e : v1)
//        {
//            cout << e << ' ';
//        }
//        cout << endl;
//    }
//}
//// 64 位输出请用 printf("%lld")


////mp3光标位置
//#include <iostream>
//using namespace std;
//
//int main() {
//    int num = 0;
//    cin >> num;
//    int index = 1;
//    if (num <= 4)
//    {
//        char c;
//        while (cin >> c)
//        {
//            if (c == 'U')
//                index--;
//            else if (c == 'D')
//                index++;
//            index = (index + num) % num;
//        }
//        for (int i = 1; i <= num; i++)
//            cout << i << ' ';
//        cout << endl;
//        cout << index << endl;
//        return 0;
//    }
//    else
//    {
//        char c;
//        int start = 1;
//        int end = 1;
//        while (cin >> c)
//        {
//            if (c == 'U')
//            {
//                //特殊翻页
//                if (index == 1)
//                {
//                    start = num - 3;
//                    end = num;
//                    index = num;
//                }
//                else if (index - start == 0 && end - index == 3)
//                {
//                    start--; end--; index--;
//                }
//                else
//                {
//                    index--;
//                }
//            }
//            else if (c == 'D')
//            {
//                //特殊翻页
//                if (index == num)
//                {
//                    start = 1;
//                    end = 4;
//                    index = 1;
//                }
//                else if (index - start == 3 && end - index == 0)
//                {
//                    start++; end++; index++;
//                }
//                else {
//                    index++;
//                }
//            }
//        }
//        for (int i = start; i <= end; i++)
//            cout << i << ' ';
//        cout << endl;
//        cout << index;
//        return 0;
//    }
//}
//// 64 位输出请用 printf("%lld")

class Solution {
public:
    int search(vector<int>& nums, int target) {
        // 初始化 left 与 right 指针
        int left = 0, right = nums.size() - 1;
        // 由于两个指针相交时，当前元素还未判断，因此需要取等号
        while (left <= right)
        {
            // 先找到区间的中间元素
            int mid = left + (right - left) / 2;//加不加1无所谓
            // 分三种情况讨论
            if (nums[mid] < target) left = mid + 1;
            else if (nums[mid] > target) right = mid - 1;
            else return mid;
        }
        // 如果程序⾛到这⾥，说明没有找到⽬标值，返回 -1
        return -1;
    }
};
